home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / rbmap.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  10.9 KB  |  432 lines
  1. /*
  2.   File: RBMap.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12.  
  13. */
  14.   
  15. package collections;
  16.  
  17. import java.util.Enumeration;
  18. import java.util.NoSuchElementException;
  19.  
  20. /**
  21.  *
  22.  *
  23.  * RedBlack Trees of (key, element) pairs
  24.  * @author Doug Lea
  25.  * @version 0.93
  26.  *
  27.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  28. **/
  29.  
  30.   
  31. public class RBMap extends    UpdatableMapImpl 
  32.                    implements UpdatableMap, 
  33.                               KeySortedCollection {
  34.  
  35. // instance variables
  36.  
  37. /**
  38.  * The root of the tree. Null iff empty.
  39. **/
  40.  
  41.   protected RBPair tree_;
  42.  
  43. /**
  44.  * The comparator to use for ordering
  45. **/
  46.  
  47.   protected Comparator cmp_;
  48.  
  49. /**
  50.  * Make an empty tree, using DefaultComparator for ordering
  51. **/
  52.  
  53.   public RBMap() { this(null, null, null, 0); }
  54.  
  55.  
  56. /**
  57.  * Make an empty tree, using given screener for screening elements (not keys)
  58. **/
  59.   public RBMap(Predicate screener) { this(screener, null, null, 0); }
  60.  
  61. /**
  62.  * Make an empty tree, using given Comparator for ordering
  63. **/
  64.   public RBMap(Comparator c) { this(null, c, null, 0); }
  65.  
  66. /**
  67.  * Make an empty tree, using given screener and Comparator.
  68. **/
  69.   public RBMap(Predicate s, Comparator c) { this(s, c, null, 0); }
  70.  
  71. /**
  72.  * Special version of constructor needed by clone()
  73. **/
  74.  
  75.   protected RBMap(Predicate s, Comparator cmp, RBPair t, int n) { 
  76.     super(s); 
  77.     count_ = n;
  78.     tree_ = t;
  79.     if (cmp != null) cmp_ = cmp;
  80.     else cmp_ = new DefaultComparator();
  81.   }
  82.  
  83. /**
  84.  * Create an independent copy. Does not clone elements.
  85. **/
  86.  
  87.   protected Object clone() throws CloneNotSupportedException { 
  88.     if (count_ == 0) return new RBMap(screener_, cmp_);
  89.     else return new RBMap(screener_, cmp_, (RBPair)(tree_.copyTree()), count_);
  90.   }
  91.  
  92.  
  93. // Collection methods
  94.  
  95. /**
  96.  * Implements collections.Collection.includes.
  97.  * Time complexity: O(log n).
  98.  * @see collections.Collection#includes
  99. **/
  100.   public synchronized boolean includes(Object element) {
  101.     if (element == null || count_ == 0) return false;
  102.     return tree_.find(element, cmp_) != null;
  103.   }
  104.  
  105. /**
  106.  * Implements collections.Collection.occurrencesOf.
  107.  * Time complexity: O(log n).
  108.  * @see collections.Collection#occurrencesOf
  109. **/
  110.   public synchronized int occurrencesOf(Object element) {
  111.     if (element == null || count_ == 0) return 0;
  112.     return tree_.count(element, cmp_);
  113.   }
  114.  
  115. /**
  116.  * Implements collections.Collection.elements.
  117.  * Time complexity: O(1).
  118.  * @see collections.Collection#elements
  119. **/
  120.   public synchronized CollectionEnumeration elements() { 
  121.     return new RBPairEnumeration(this, tree_, false);
  122.   }
  123.  
  124. // KeySortedCollection methods
  125.  
  126. /**
  127.  * Implements collections.KeySortedCollection.keyComparator
  128.  * Time complexity: O(1).
  129.  * @see collections.KeySortedCollection#keyComparator
  130. **/
  131.   public synchronized Comparator keyComparator() { return cmp_; }
  132.  
  133. /**
  134.  * Use a new comparator. Causes a reorganization
  135. **/
  136.  
  137.   public synchronized void comparator(Comparator cmp) {
  138.     if (cmp != cmp_) {
  139.       if (cmp != null) cmp = cmp;
  140.       else cmp_ = new DefaultComparator();
  141.       if (count_ != 0) {       // must rebuild tree!
  142.         incVersion();
  143.         RBPair t = (RBPair) (tree_.leftmost());
  144.         tree_ = null;
  145.         count_ = 0;
  146.         while (t != null) {
  147.           add_(t.key(), t.element(), false);
  148.           t = (RBPair)(t.successor());
  149.         }
  150.       }
  151.     }
  152.   }
  153.  
  154. // Map methods
  155.  
  156.  
  157. /**
  158.  * Implements collections.Map.includesKey.
  159.  * Time complexity: O(log n).
  160.  * @see collections.Map#includesKey
  161. **/
  162.   public synchronized boolean  includesKey(Object key) {
  163.     if (key == null || count_ == 0) return false;
  164.     return tree_.findKey(key, cmp_) != null;
  165.   }
  166.  
  167. /**
  168.  * Implements collections.Map.includes.
  169.  * Time complexity: O(n).
  170.  * @see collections.Map#includes
  171. **/
  172.   public synchronized boolean includesAt(Object key, Object element) {
  173.     if (key == null || element == null || count_ == 0) return false;
  174.     return tree_.find(key, element, cmp_) != null;
  175.   }
  176.  
  177. /**
  178.  * Implements collections.Map.keys.
  179.  * Time complexity: O(1).
  180.  * @see collections.Map#keys
  181. **/
  182.   public synchronized CollectionEnumeration keys() { 
  183.     return new RBPairEnumeration(this, tree_, true); 
  184.   }
  185.  
  186. /**
  187.  * Implements collections.Map.at.
  188.  * Time complexity: O(log n).
  189.  * @see collections.Map#at
  190. **/
  191.   public synchronized Object at(Object key) 
  192.   throws  NoSuchElementException {
  193.     if (count_ != 0) {
  194.       RBPair p = tree_.findKey(key, cmp_);
  195.       if (p != null) return p.element();
  196.     }
  197.     throw new NoSuchElementException("no Key matching argument " + key);
  198.   }
  199.  
  200. /**
  201.  * Implements collections.Map.aKeyOf.
  202.  * Time complexity: O(n).
  203.  * @see collections.Map#aKeyOf
  204. **/
  205.   public synchronized Object aKeyOf(Object element) {
  206.     if (element == null || count_ == 0) return null;
  207.     RBPair p = ((RBPair)( tree_.find(element, cmp_)));
  208.     if (p != null) 
  209.       return p.key();
  210.     else
  211.       return null;
  212.   }
  213.  
  214.  
  215. // UpdatableCollection methods
  216.  
  217. /**
  218.  * Implements collections.UpdatableCollection.clear.
  219.  * Time complexity: O(1).
  220.  * @see collections.UpdatableCollection#clear
  221. **/
  222.   public synchronized void clear() { 
  223.     setCount(0);
  224.     tree_ = null;
  225.   }
  226.  
  227.  
  228. /**
  229.  * Implements collections.UpdatableCollection.exclude.
  230.  * Time complexity: O(n).
  231.  * @see collections.UpdatableCollection#exclude
  232. **/
  233.   public synchronized void exclude(Object element) {
  234.     if (element == null || count_ == 0) return;
  235.     RBPair p = (RBPair)(tree_.find(element, cmp_));
  236.     while (p != null) {
  237.       tree_ = (RBPair)(p.delete(tree_));
  238.       decCount();
  239.       if (count_ == 0) return;
  240.       p = (RBPair)(tree_.find(element, cmp_));
  241.     }
  242.   }
  243.  
  244. /**
  245.  * Implements collections.UpdatableCollection.removeOneOf.
  246.  * Time complexity: O(n).
  247.  * @see collections.UpdatableCollection#removeOneOf
  248. **/
  249.   public synchronized void removeOneOf(Object element) {
  250.     if (element == null || count_ == 0) return;
  251.     RBPair p = (RBPair)(tree_.find(element, cmp_));
  252.     if (p != null) {
  253.       tree_ = (RBPair)(p.delete(tree_));
  254.       decCount();
  255.     }
  256.   }
  257.       
  258.  
  259. /**
  260.  * Implements collections.UpdatableCollection.replaceOneOf.
  261.  * Time complexity: O(n).
  262.  * @see collections.UpdatableCollection#replaceOneOf
  263. **/
  264.   public synchronized void replaceOneOf(Object oldElement, Object newElement) 
  265.   throws IllegalElementException {
  266.     if (count_ == 0 || oldElement == null || oldElement.equals(newElement))
  267.       return;
  268.     RBPair p = (RBPair)(tree_.find(oldElement, cmp_));
  269.     if (p != null) {
  270.       checkElement(newElement);
  271.       incVersion();
  272.       p.element(newElement);
  273.     }
  274.   }
  275.  
  276. /**
  277.  * Implements collections.UpdatableCollection.replaceAllOf.
  278.  * Time complexity: O(n).
  279.  * @see collections.UpdatableCollection#replaceAllOf
  280. **/
  281.   public synchronized void replaceAllOf(Object oldElement, Object newElement) 
  282.   throws IllegalElementException {
  283.     RBPair p = (RBPair)(tree_.find(oldElement, cmp_));
  284.     while (p != null) {
  285.       checkElement(newElement);
  286.       incVersion();
  287.       p.element(newElement);
  288.       p = (RBPair)(tree_.find(oldElement, cmp_));
  289.     }
  290.   }
  291.  
  292. /**
  293.  * Implements collections.UpdatableCollection.take.
  294.  * Time complexity: O(log n).
  295.  * Takes the element associated with the least key.
  296.  * @see collections.UpdatableCollection#take
  297. **/
  298.   public synchronized Object take() 
  299.   throws NoSuchElementException {
  300.     if (count_ != 0) {
  301.       RBPair p = (RBPair)(tree_.leftmost());
  302.       Object v = p.element();
  303.       tree_ = (RBPair)(p.delete(tree_));
  304.       decCount();
  305.       return v;
  306.     }
  307.     checkIndex(0);
  308.     return null; // not reached
  309.   }
  310.  
  311.  
  312. // UpdatableMap methods
  313.  
  314. /**
  315.  * Implements collections.UpdatableMap.putAt.
  316.  * Time complexity: O(log n).
  317.  * @see collections.UpdatableMap#putAt
  318. **/
  319.   public synchronized void putAt(Object key, Object element) {
  320.     add_(key, element, true);
  321.   }
  322.  
  323.  
  324. /**
  325.  * Implements collections.UpdatableMap.removeAt.
  326.  * Time complexity: O(log n).
  327.  * @see collections.UpdatableMap#removeAt
  328. **/
  329.   public synchronized void removeAt(Object key) {
  330.     if (key == null || count_ == 0) return;
  331.     RBCell p = tree_.findKey(key, cmp_);
  332.     if (p != null) {
  333.       tree_ = (RBPair)(p.delete(tree_));
  334.       decCount();
  335.     }
  336.   }
  337.  
  338.  
  339. /**
  340.  * Implements collections.UpdatableMap.replaceElement.
  341.  * Time complexity: O(log n).
  342.  * @see collections.UpdatableMap#replaceElement
  343. **/
  344.   public synchronized void replaceElement(Object key, Object oldElement, 
  345.                                           Object newElement)  
  346.   throws IllegalElementException { 
  347.     if (key == null || oldElement == null || count_ == 0) return;
  348.     RBPair p = tree_.find(key, oldElement, cmp_);
  349.     if (p != null) {
  350.       checkElement(newElement);
  351.       p.element(newElement);
  352.       incVersion();
  353.     }
  354.   }
  355.  
  356.  
  357. // helper methods
  358.  
  359.  
  360.   private void add_(Object key, Object element, boolean checkOccurrence) 
  361.   throws IllegalElementException {
  362.     checkKey(key);
  363.     checkElement(element);
  364.     if (tree_ == null) {
  365.       tree_ = new RBPair(key, element);
  366.       incCount();
  367.     }
  368.     else {
  369.       RBPair t = tree_;
  370.       for (;;) {
  371.         int diff = cmp_.compare(key, t.key());
  372.         if (diff == 0  && checkOccurrence) {
  373.           if (!t.element().equals(element)) {
  374.             t.element(element);
  375.             incVersion();
  376.           }
  377.           return;
  378.         }
  379.         else if (diff <= 0) {
  380.           if (t.left() != null) 
  381.             t = (RBPair)(t.left());
  382.           else {
  383.             tree_ = (RBPair)(t.insertLeft(new RBPair(key, element), tree_));
  384.             incCount();
  385.             return;
  386.           }
  387.         }
  388.         else {
  389.           if (t.right() != null) 
  390.             t = (RBPair)(t.right());
  391.           else {
  392.             tree_ = (RBPair)(t.insertRight(new RBPair(key, element), tree_));
  393.             incCount();
  394.             return;
  395.           }
  396.         }
  397.       }
  398.     }
  399.   }
  400.  
  401. // ImplementationCheckable methods
  402.  
  403. /**
  404.  * Implements collections.ImplementationCheckable.checkImplementation.
  405.  * @see collections.ImplementationCheckable#checkImplementation
  406. **/
  407.   public void checkImplementation() 
  408.   throws ImplementationError {
  409.  
  410.     super.checkImplementation();
  411.     assert(cmp_ != null);
  412.     assert(((count_ == 0) == (tree_ == null)));
  413.     assert((tree_ == null || tree_.size() == count_));
  414.  
  415.     if (tree_ != null) {
  416.       tree_.checkImplementation();
  417.       Object last = null;
  418.       RBPair t = (RBPair)(tree_.leftmost());
  419.       while (t != null) {
  420.         Object v = t.key();
  421.         assert((last == null || cmp_.compare(last, v) <= 0));
  422.         last = v;
  423.         t = (RBPair)(t.successor());
  424.       }
  425.     }
  426.   }
  427.  
  428. }
  429.  
  430.  
  431.  
  432.